package com.leetcode.二叉树;

/**
 * 给定一个二叉树，找出其最大深度 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 
 * 说明: 叶子节点是指没有子节点的节点。
 * 
 * @author LZF
 *
 */
public class L104二叉树的最大深度 {
	/**
	 * 本题利用层次遍历或深度优先搜索都可以搞定。
	 * 在遍历的过程当中不断保存最大值即可。
	 * 以深搜为例：
	 * 
	 */
	public int maxDepth(TreeNode root) {
		return dfs(root);
	}
	public int dfs(TreeNode node) {
		if(node == null) return 0;
		else {
			return 1 + Math.max(dfs(node.left),dfs(node.right));
			//自己这一层是1，然后是左右子树，看哪个层数更多。
		}
	}

	// 树的定义
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}
}
